题解 CF700B Connecting Universities

发表于 | 更新于

题意：给出一棵树上的$2\times k$个节点，给他们配对，使得他们之间的距离和最大。

显然，如果对于每条边，它被经过的次数越多越好，那么它被经过的次数最多是多少呢，假设在它两侧分别有$x,y$个端点，那么它被经过的次数最多是$min(x,y)$;

所以$ans$就是$\sum min(x,y)$；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define ll long long
#define sqr(x) ((x)*(x))
using namespace std;
inline void write(ll x) {if (x<0) putchar('-'),x=-x;if (x>=10) write(x/10);putchar(x%10|'0');}
inline void wln(ll x) {write(x);puts("");}
struct node{
    ll to,next;
}e[500000];
inline ll read(){
   ll s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
ll n,k,head[500000],cnt,t[500000],b[500000],a[500000],ans;
inline void add(ll u,ll v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(ll u,ll fa){
    if (b[u])t[u]=1;
    for (ll i=head[u];i;i=e[i].next){
        ll v=e[i].to;
        if (v==fa)continue;
        dfs(v,u);
        t[u]+=t[v];
    }
    ans+=min(t[u],2*k-t[u]);
}
int main(){
    n=read(),k=read();
    for (ll i=1;i<=2*k;++i)
        a[i]=read(),b[a[i]]=1;;
    for (ll i=1;i<=n-1;++i){
        ll u=read(),v=read();
        add(u,v);add(v,u);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}